{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉树中和为目标值的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #backtracking #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #回溯 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pathTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中和为目标值的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根节点 <code>root</code> 和一个整数目标和 <code>targetSum</code> ，找出所有 <strong>从根节点到叶子节点</strong> 路径总和等于给定目标和的路径。</p>\n",
    "\n",
    "<p><strong>叶子节点</strong> 是指没有子节点的节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22\n",
    "<strong>输出：</strong>[[5,4,11,2],[5,8,4,5]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3], targetSum = 5\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2], targetSum = 0\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点总数在范围 <code>[0, 5000]</code> 内</li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "\t<li><code>-1000 &lt;= targetSum &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 113&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/path-sum-ii/\">https://leetcode-cn.com/problems/path-sum-ii/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof](https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof](https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,8,11,null,13,4,7,2,null,null,5,1]\\n22', '[]\\n1', '[]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def __init__(self):\n",
    "#         self.path = []\n",
    "#         self.res = []\n",
    "\n",
    "#     def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "#         if not root:\n",
    "#             return []\n",
    "#         self.path.append(root.val)\n",
    "#         diff = target-root.val\n",
    "#         if not root.left and not root.right:\n",
    "#             if diff == 0:\n",
    "#                 self.res.append(self.path.copy())\n",
    "#         if root.left:\n",
    "#             self.pathTarget(root.left, diff)\n",
    "#         if root.right:\n",
    "#             self.pathTarget(root.right, diff)\n",
    "#         self.path.pop()\n",
    "#         return self.res\n",
    "\n",
    "\n",
    "import queue\n",
    "class Solution:        \n",
    "    def pathTarget(self , root: TreeNode, target: int) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        s = queue.Queue()\n",
    "        s.put((root, [root.val], root.val))   # 利用元组记录到达每一个节点时的路径和总和，在稍后弹出时不用担心前面节点的信息被遗忘\n",
    "        res = []\n",
    "        while not s.empty():\n",
    "            node, path, val = s.get()   # 队首的节点信息，其中val表示到达当前节点时的总和\n",
    "            if node and not node.left and not node.right:   # 到达叶节点，判断目标值是否满足\n",
    "                if val == target:\n",
    "                    res.append(path)\n",
    "            # 左右子树递归，依次加入左右子节点，然后进入下一层，弹出时再把新的左右子节点加进来\n",
    "            if node.left:\n",
    "                s.put((node.left, path+[node.left.val], val+node.left.val))   # 更新节点，路径，总和\n",
    "            if node.right:\n",
    "                s.put((node.right, path+[node.right.val], val+node.right.val))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        \n",
    "        res=[]\n",
    "        def process(root,target,l):\n",
    "            if not root:\n",
    "                return\n",
    "            l.append(root.val)\n",
    "            target-=root.val\n",
    "            if not root.left and not root.right:\n",
    "                if target==0:\n",
    "                    res.append(list(l))\n",
    "                l.pop()\n",
    "                return\n",
    "            process(root.left,target,l)\n",
    "            process(root.right,target,l)\n",
    "            l.pop()\n",
    "            \n",
    "        process(root,target,[])\n",
    "        return res\n",
    "\n",
    "           \n",
    "                \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        queue.append((root, root.val, [root.val]))\n",
    "        while queue:\n",
    "            info = queue.popleft()\n",
    "            if info[0].left: queue.append((info[0].left, info[1] + info[0].left.val, info[2] + [info[0].left.val]))\n",
    "            if info[0].right: queue.append((info[0].right, info[1] + info[0].right.val, info[2] + [info[0].right.val]))\n",
    "            if not info[0].left and not info[0].right and info[1] == target:\n",
    "                res.append(info[2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(root, target):\n",
    "            if not root:\n",
    "                return None\n",
    "            path.append(root.val)\n",
    "            target -= root.val\n",
    "            if not root.left and not root.right and target == 0:\n",
    "                ans.append(path[:])\n",
    "            dfs(root.left, target)\n",
    "            dfs(root.right, target)\n",
    "            path.pop()\n",
    "        dfs(root, target)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        # # bfs\n",
    "        # res = []\n",
    "        # que = deque()\n",
    "        # que.append((root, [], 0)) # 将要处理的节点，路径，路径和\n",
    "        # while que:\n",
    "        #     node, path, pathSum = que.popleft()\n",
    "        #     if not node: # 如果是空节点，不处理\n",
    "        #         continue\n",
    "        #     if not node.left and not node.right: # 如果是叶子节点\n",
    "        #         if node.val + pathSum == target: # 加上叶子节点后，路径和等于target\n",
    "        #             res.append(path + [node.val]) # 保存路径\n",
    "        #     # 处理左子树\n",
    "        #     que.append((node.left, path + [node.val], pathSum + node.val))\n",
    "        #     # 处理右子树\n",
    "        #     que.append((node.right, path + [node.val], pathSum + node.val))\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        res, path = [], []\n",
    "        def recur(root, tar):\n",
    "            if not root:return\n",
    "            path.append(root.val)\n",
    "            tar -= root.val\n",
    "            if tar == 0 and not root.left and not root.right:\n",
    "                res.append(list(path))\n",
    "            recur(root.left, tar)\n",
    "            recur(root.right, tar)\n",
    "            path.pop()\n",
    "\n",
    "        recur(root, target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        def dfs(node, target):\n",
    "            if not node:\n",
    "                return\n",
    "            target -= node.val\n",
    "            path.append(node.val)\n",
    "            if not node.left and not node.right and target == 0:\n",
    "                output.append(list(path))\n",
    "                #return \n",
    "            # node.left and target != 0:\n",
    "            dfs(node.left, target)\n",
    "            #  node.right and target != 0:\n",
    "            dfs(node.right, target)\n",
    "            path.pop()\n",
    "        output = []\n",
    "        path = []\n",
    "        dfs(root, target)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        def getAllPaths(root, target):\n",
    "            if root == None:\n",
    "                return []\n",
    "            \n",
    "            if root.left ==  None and root.right == None and target == root.val:\n",
    "                    return [[root.val]]\n",
    "\n",
    "            result1 = getAllPaths(root.left,  target - root.val)\n",
    "            result2 = getAllPaths(root.right, target - root.val)\n",
    "            \n",
    "            result = []\n",
    "            for item in result1:\n",
    "                result.append([root.val] + item)\n",
    "            for item in result2:\n",
    "                result.append([root.val] + item)\n",
    "            \n",
    "            return result\n",
    "\n",
    "        result = getAllPaths(root, target)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        def backtrack(ans:List,path:List,cur,remain:int):\n",
    "            if not cur: return \n",
    "            if cur.val== remain and not cur.left and not cur.right:\n",
    "                ans.append((path+[cur.val]).copy())\n",
    "                return \n",
    "            path.append(cur.val)\n",
    "            # 递归左右子树\n",
    "            backtrack(ans, path, cur.left, remain - cur.val)\n",
    "            backtrack(ans, path, cur.right, remain - cur.val)\n",
    "            # 撤销选择\n",
    "            path.pop(-1)\n",
    "        ans = []\n",
    "        # 入口，路径，目标值全部传进去，其中路径和path都是扩展的参数\n",
    "        backtrack(ans, [], root, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        res, path = [], []\n",
    "        def recur(root, tar):\n",
    "            if not root:return\n",
    "            path.append(root.val)\n",
    "            tar -= root.val\n",
    "            if tar == 0 and not root.left and not root.right:\n",
    "                res.append(list(path))\n",
    "            recur(root.left, tar)\n",
    "            recur(root.right, tar)\n",
    "            path.pop()\n",
    "\n",
    "        recur(root, target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        res,path=[],[]\n",
    "        def recur(root, tar):\n",
    "            if not root:return\n",
    "            path.append(root.val)\n",
    "            tar-=root.val\n",
    "            if tar==0 and not root.left and not root.right:\n",
    "                res.append(list(path))            \n",
    "            recur(root.left,tar)\n",
    "            recur(root.right,tar)\n",
    "            path.pop()\n",
    "        recur(root,target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        t_ans = []\n",
    "        def dfs(node,res):\n",
    "            if not node: return\n",
    "            t_ans.append(node.val)\n",
    "            res+=node.val\n",
    "            if res==target and not node.left and not node.right:\n",
    "                ans.append(list(t_ans))\n",
    "                print(ans)\n",
    "            dfs(node.left,res)\n",
    "            dfs(node.right,res)\n",
    "            t_ans.pop()\n",
    "\n",
    "        dfs(root,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        path = []\n",
    "        ans = []\n",
    "        def f(o):\n",
    "            if not o: return\n",
    "            path.append(o.val)\n",
    "            if sum(path) == target and not o.left and not o.right: ans.append(deepcopy(path))\n",
    "            f(o.left)\n",
    "            f(o.right)\n",
    "            path.pop()\n",
    "        f(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        t_ans = []\n",
    "        def dfs(node,res):\n",
    "            if not node: return\n",
    "            t_ans.append(node.val)\n",
    "            res+=node.val\n",
    "            if res==target and not node.left and not node.right:\n",
    "                ans.append(list(t_ans))\n",
    "                print(ans)\n",
    "            dfs(node.left,res)\n",
    "            dfs(node.right,res)\n",
    "            t_ans.pop()\n",
    "\n",
    "        dfs(root,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        output = []\n",
    "        def dfs(node, lists, sums):\n",
    "            if node.left is None and node.right is None:  #叶子节点\n",
    "                if sums + node.val == target:\n",
    "                    output.append(lists + [node.val])\n",
    "                return \n",
    "            if node.left:\n",
    "                dfs(node.left, lists + [node.val], sums + node.val)\n",
    "            if node.right:\n",
    "                dfs(node.right, lists + [node.val], sums + node.val)\n",
    "        dfs(root, [], 0)\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        def path(root, _sum, nodes):\n",
    "            if not root:\n",
    "                return \n",
    "            \n",
    "            if not root.left and not root.right:\n",
    "                if target == _sum + root.val:\n",
    "                    ans.append(nodes + [root.val])\n",
    "            if root.left:\n",
    "                path(root.left, _sum + root.val, nodes + [root.val])\n",
    "            if root.right:\n",
    "                path(root.right, _sum + root.val, nodes + [root.val])\n",
    "\n",
    "        path(root, 0, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        res = []\n",
    "        def dfs(node, nums):\n",
    "            if node.left is None and node.right is None:    #遍历到根节点\n",
    "                nums.append(node.val)\n",
    "                if sum(nums)==target:\n",
    "                    nonlocal res\n",
    "                    res.append(nums)\n",
    "            else:\n",
    "                if node.left is not None:\n",
    "                    dfs(node.left, nums+[node.val])\n",
    "                if node.right is not None:\n",
    "                    dfs(node.right, nums+[node.val])\n",
    "\n",
    "        dfs(root, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        if root is None:return []\n",
    "        result,path = [],[]\n",
    "        def dfs(root,tar,result,path):\n",
    "            if root is None:\n",
    "                return\n",
    "            path = path+[root.val] # 关键点 写成path.append(root.val)是错误的\n",
    "            if tar-root.val == 0 and not root.left and not root.right: # not root.left and not root.right 保证到叶子节点\n",
    "                result.append(path)\n",
    "                return \n",
    "             #寻找全部符合条件的路径\n",
    "            '''\n",
    "            if dfs(root.left,node,path) or dfs(root.right,node,path): #只找一条符合条件的路径即可\n",
    "                return True\n",
    "            '''\n",
    "            dfs(root.left,tar-root.val,result,path)\n",
    "            dfs(root.right,tar-root.val,result,path)\n",
    "            # path.pop() #关键 不合适则弹出\n",
    "        dfs(root,target,result,path)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        answer = []\n",
    "        def dfs(inputNode, val_list):\n",
    "            if inputNode is not None:\n",
    "                val_list = val_list+[inputNode.val]\n",
    "                if sum(val_list) == target and inputNode.right is None and inputNode.left is None:\n",
    "                    answer.append(val_list)\n",
    "                dfs(inputNode.left, val_list)\n",
    "                dfs(inputNode.right, val_list)\n",
    "        dfs(root, [])\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        def dfs(root,target,paths,path):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                if target==root.val:\n",
    "                    paths.append(path+[root.val])\n",
    "            dfs(root.left,target-root.val,paths,path+[root.val])\n",
    "            dfs(root.right,target-root.val,paths,path+[root.val])\n",
    "        path,paths=[],[]\n",
    "        dfs(root,target,paths,path)\n",
    "        return paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        if root is None or target is None:\n",
    "            return []\n",
    "        self.ans = []\n",
    "        path = [] \n",
    "        self.bfs(root,target,path)\n",
    "        return self.ans \n",
    "\n",
    "    def bfs(self, root, target, path):\n",
    "        if root is None:\n",
    "            return \n",
    "        if root.left is None and root.right is None:\n",
    "            if root.val == target:\n",
    "                path.append(root.val)\n",
    "                self.ans.append(path)\n",
    "            else:\n",
    "                return \n",
    "        \n",
    "        self.bfs(root.left, target-root.val, path+[root.val])\n",
    "        self.bfs(root.right, target-root.val, path+[root.val])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        def run(root, sum, layers):\n",
    "            if not root.left and not root.right and root.val == sum:\n",
    "                res.append(layers[:] + [root.val])\n",
    "            if root.left: run(root.left, sum - root.val, layers+[root.val])\n",
    "            if root.right: run(root.right, sum - root.val, layers+[root.val])\n",
    "        if root:\n",
    "            run(root, target, [])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
